package com.example.myletcodelearing.one

import com.example.myletcodelearing.kmp.KmpTest
import java.util.*
import kotlin.math.max

/**
 * @author tgw
 * @date 2022/9/30
 * @describe
 */
fun main(array: Array<String>) {
    val ss = "abcabcbb"
    var length = Solution3().lengthOfLongestSubstring(ss)
    var length2 = Solution3().lengthOfLongestSubstring2(ss)
    var length3 = Solution3().lengthOfLongestSubstring3(ss)
    print("长度：$length")
    print("长度：$length2")
    print("长度：$length3")

}

private class Solution3 {
    fun lengthOfLongestSubstring(s: String): Int {
        // 记录字符上一次出现的位置
        val last = IntArray(128)
        for (i in 0..127) {
            last[i] = -1
        }
        val n = s.length
        var res = 0
        var start = 0 // 窗口开始位置
        for (i in 0 until n) {
            val index = s[i].toInt()
            start = Math.max(start, last[index] + 1)
            res = Math.max(res, i - start + 1)
            last[index] = i
        }

        return res
    }


    fun lengthOfLongestSubstring2(s: String): Int {
        // 记录字符上一次出现的位置
        val array = s.toCharArray()
        var hashSet = LinkedList<Char?>()

        var index = 0
        var lastIndex = 0
        for (i in array.indices) {
            var existIndex = hashSet.indexOf(array[i])+1
            if (existIndex>0) {
                if (index >= lastIndex){
                    lastIndex = index
                }
                index = index-existIndex
                while (existIndex>0){
                    hashSet.removeAt(0)
                    existIndex--
                }
            }
            index++
            hashSet.add(array[i])
        }
        lastIndex =  Math.max(index,lastIndex)
        return lastIndex
    }

    fun lengthOfLongestSubstring3(s: String): Int {
        if (s.length <= 1) {
            return s.length
        }
        var low = 0
        var max = 1
        val m = s.toCharArray()
        for (i in 1 until m.size) {
            for (j in low until i) {
                if (m[i] == m[j]) {
                    low = j + 1
                    break
                }
            }
            max = if (max > i - low + 1) max else i - low + 1
        }
        return max
    }
}